Rule-based artificial intelligence systems, generally known as expert systems, typically comprise a set of rules, one or more facts or data in a working memory, and an inference engine that applies the rules to the facts in the working memory.
The basic computations performed by a rule-based artificial intelligence system are pattern matching searches among facts or data in working memory. Facts in working memory are organized into "Working Memory Elements" (WMEs). Each WME is a set of related facts or data, such as the address, age, and sex, of an individual. Each data entry in the WME comprises one or more data fields known as "slots". WMEs are identified by "class name"; slots are also identified by name (e.g. "employee").
A rule comprises a set of conditions and a set of action instructions to be completed, if a group of facts in working memory meet all conditions of a particular rule. A rule's condition set is commonly referred to as the "left-hand side" of the rule, and the action instruction set is commonly referred to as the "right-hand side" of the rule. If the conditions of a rule match the facts, the left-hand conditions are said to be satisfied and the right-hand actions are now ready to be invoked or "fired". Only when the left-hand side conditions of a rule are met will the right-hand side action instruction set be invoked.
A condition is a test comparing data items in working memory against other WME data, fixed values or variables. Condition tests can be created using one or more relational operators including but not limited to: "=" (equal to), "&lt;" (less than), "&gt;" (greater than), "&lt;=" (less than or equal to), "&gt;=" (greater than or equal to), and "&lt;&gt;" (not equal to). A condition identifies the facts to be tested in working memory by WME. Each WME is identified by a class name, and each slot is identified by a slot name. A condition identifies a WME by class name, one or more slots to compare by slot name, and, optionally, a set of relational limits or requirements to test the values in each selected slot. Rule conditions are linked by logical connectors such as, for example "and", and "or". A set of one or more conditions, linked by one or more logical connectors, comprises the "left-hand side" of a rule. Action instruction sets comprise operations to be performed when facts in working memory match the conditions of a rule. Those operations include, for example, the addition, deletion or modification of the facts in working memory. The operations can also include transmission of the results to a user.
Programmers use programming languages, such as, for example, the language known as "OPS5" to define and create rules and WMEs for expert systems. For further background information on OPS5, the reader is referred to the following publications that are hereby expressly incorporated by reference: Programming Expert Systems in OPS5, (Addison-Wesley Publishing Co., 1985); Charles L. Forgy, OPS5-User Manual, Technical Report CMU-CS-81-135, Computer Science Department, Carnegie Mellon University, Pittsburgh, Pa., July 1981. An example of a rule using the OPS5 language is:
______________________________________ (P Rule-Example (patient-data AGE &lt;A&gt; HEIGHT {&lt;B&gt; &lt; &lt;A&gt;} NAME &lt;N&gt;) (monitor-data NAME &lt;N&gt; PULSE {&lt;C&gt; &gt; &lt;B&gt;}) .fwdarw. (Write .vertline.Patient.vertline. &lt;N&gt; .vertline.is in critical condition.vertline. ______________________________________
The left-hand side of the rule executes conditions on data of two WME classes. The first WME class, "patient data," has attributes "AGE," "HEIGHT," and "NAME" that are represented by the variables "&lt;A&gt;", "&lt;B&gt;", and "&lt;N&gt;", respectively. Those variables refer to the attributes of a specific patient. The second WME class, "monitor-data", has attributes "NAME" and "PULSE", represented by the variables "&lt;N&gt;" and "&lt;C&gt;", respectively. Those variables also denote attributes for the patient referred to in a WME definition.
The left-hand side of the rule above is satisfied when: 1) the name slot has the same value in both WMEs of class patient-data and monitor-data; 2) the patient's height is greater than the patient's age; and 3) the patient's pulse rate is greater than the patient's height. If it is determined that the left-hand side of the rule is satisfied, then the right-hand side of the rule can be executed. The message, "Patient [name (e.g. John Doe)]is in critical condition," is written to a device such as a display terminal.
Inference engines are comprised of data processing devices, such as a computer, and programmed elements or subroutines to perform a condition matching and "firing" sequence for each specified rule, using the facts in working memory. The condition-matching/firing sequence is sometimes referred to as a "recognize/act" cycle. "Recognize" refers to the left-hand portion of the operation, where the inference engine invokes subroutines of programmed elements to apply the conditions of the rules to the data in working memory to determine which, if any, rules to fire. "Act" refers to the right-hand portion of the operation, where the inference engine performs the action set specified in the rule (i.e. fires).
The inference engine performs left-hand condition testing by matching the data in working memory to the specifications of the condition test. In the comparison operation, the inference engine determines whether the named WME contains an entry whose slot values correspond to the slot values set forth in the condition. If so, the condition is satisfied. However, if working memory does not have an entry whose slot contains the values specified in the condition, the condition is not satisfied. To determine whether a rule will fire, the inference engine performs the existence test in connection with each condition in the rule.
Comparison or recognition tests can become more complicated when a rule contains one or more conditions with slot values expressed as variables. If a condition identifies a WME class and one or more slot values, at least one of which is specified by a variable, and the values identified for each of the other slot names match the values in the corresponding slots in the working memory entry, the condition is satisfied by each entry in the relation identified by the class name in which the variable is satisfied. In the case of a match operation for a condition with a variable, the inference engine establishes one or more binding lists for the variables, identifying the set of slot value in the various WMEs which can satisfy the condition. The values of the variables in each binding list are propagated through subsequent conditions.
One present problem in implementing rule-based expert systems is finding an efficient method to execute the many rules that would comprise a large expert system. One way that an inference engine can determine if the expert system rules' conditions are satisfied is to test each condition of each rule against data in working memory and track the rules whose conditions are satisfied. That method will affect many redundant comparisons because in many circumstances the same condition is included in many different rules.
Further, it is usually unnecessary to evaluate every WME against every rule during every recognitionact cycle. Instead, partial lists of rule matches can be maintained and incremental updates can be performed on those lists as relations are added, deleted or modified.
To avoid the necessity of testing and retesting conditions for each rule, the rules comprising an expert system can be organized into a "discrimination network", such as a "reticular" discrimination network, also known as a "RETE-net". A RETE-net comprises a series of interconnected nodes. The nodes are programmed elements representing facets of the user-defined rules. In a RETE-net, the conditions of all the rules are organized as a series of either one or two input "test" nodes.
A one-input test node accepts input from only one source and compares the input against constant or pre-defined variables. A one-input test node can be associated with different conditions found in a rule. For example, the condition "A&lt;3" is represented by a one-input node referred to as a test node. A condition is represented by a single test node even if that condition occurs in the left-hand side of multiple rules.
One-input test nodes receive WME slot data, and compare the data against fixed values. Successful relation entries are passed as "tokens" by test nodes to respective superseding join nodes or test nodes.
The test nodes are interconnected by a series of two-input "join" nodes. Each join node represents a logical connection between the conditions found on the left-hand side of each rule.
Two-input nodes accept variable input from two different sources and compare the two different source inputs on pre-determined matching criteria.
Two-input join nodes maintain lists that record the set of WMEs data received by the node in memory. Because two-input nodes compare series of inputs against each other, the input is stored in memories. Unlike a one-input node which has no memory, join nodes comprise two associated memories known as "alpha" and "beta" memories--One memory collects and stores input from each of the nodes' feeding tokens. Two-input join nodes represent a logical connection of two conditional expressions (e.g., (A&lt;B) and (A&gt;0)). "Beta" memory entries at any particular node represent a set of facts that satisfy the test conditions to the left of the logical connector represented by the join node. Entries in the "Alpha" memory represent conditions satisfy conditions the right of the logical connector represented in the join node.
A typical rule-based expert system includes a number of rules. A RETE-net created for an expert system will have a plurality of test nodes, one for each condition in the rules, so that if the same condition appears in multiple rules, the RETE-net requires only one test node to represent the condition. In addition, join nodes may be shared among rules if the same series of preceding join nodes and test conditions are used in multiple rules. Following a join node may be other test nodes, join nodes or a terminal node.
When WMEs are added to the RETE-net or when WME facts are modified, the changes are propagated through the RETE-net by tokens that are passed between test and join nodes. There are two types of tokens: add and delete tokens. Add-tokens signal to the node that evaluates the date referenced by the tokens that the value is new and must be processed against the rule conditions. A delete token signals to each node to delete any stored references to the data referenced by the delete token.
WME data is initially introduced to the RETE-net as a series of add-tokens. The first step is to pass the token to each test node, constructed to compare the data referenced. For each successful test, the testing node passes a token containing the data update to its successor. If the test fails using the new data, the data is not sent for further processing. This sequence of passing and testing the token continues until the token either fails a test or reaches a terminal node.
A rule is ready to be fired once a successful token reaches a terminal node. A terminal node comprises the right-hand side of the action instruction set that should fire when the left-hand side conditions of a rule are satisfied. Because a rule-based expert system typically comprises many rules, a RETE-net correspondingly comprises a number of terminal nodes. In a RETE-net, many terminal nodes can be ready to fire in the same cycle. Problems sometimes occur in ordering the sequence in which the inference engine will fire the terminal nodes. Some action instruction sets depend upon the results of the firing of other terminal nodes. The inference engine comprises in part, programmed elements or subroutines, known as "conflict resolution procedures" to select the order of terminal node firing.
As stated above, the action instruction set can cause changes to the working memory elements and thus change the state of the RETE-net. The changes may cause new rules to be satisfied on the left-hand side and ready to fire on the right-hand side. The changes may also cause other rules, previously satisfied on the left-hand side, to become false; its right-hand side now not ready to be fired. RETE-net expert systems employ conflict resolution modules to fire the single best rule in accordance with a fixed set of selection criteria known as the "conflict resolution strategy". The conflict resolution modules may re-arrange or cancel right-hand rule firings, depending on the re-evaluated state of the RETE-net.
A RETE-net is constructed by expressing the left-hand conditions of the rules of the expert system as a series of one- and two- input nodes, with the right- hand side action instruction set expressed as terminal nodes. RETE-nets are used by passing data through the series of nodes from node to node passing a data construct known as a token. Tokens contain pointers to both WMEs and WME slot data fields. A token is passed through the RETE-net in a top-down fashion wherein a token is first passed to RETE-net nodes that perform initial comparisons of the expert system's rules. As the data contained in the WME slots referenced by the token continue to satisfy the conditions of the rule, resident at each node, the RETE-net continues to pass tokens referencing the data into further levels of the RETE-net. If a token data reaches a terminal node, the data referenced satisfies all of the criteria of the expert system. The right-hand side of the rule will fire. To accomplish the building and updating of a RETE-net, traditional RETE-net nodes pass and accept two types of tokens--add and delete tokens. When information is newly added to the RETE-net, the addition of new information is propagated throughout the RETE-net by a series of add tokens which are created by each node when the input satisfies the node test.
However, when data in the RETE-net needs to be expunged, the data references are removed by a delete token. On receiving a delete token, each two-input node eliminates all data slots referenced by the token. The two-input node will also propagate a delete token that references the same WME to subsequent nodes in the RETE-net.
Traditional one-input nodes have no associated memories so the delete token received by a one-input node is simply forwarded to subsequent nodes.
Alterations to the data in a RETE-net is accomplished through a modification procedure. The alteration of data stored in a RETE-net is accomplished by first propagating delete tokens to remove the altered data references and then passing add-tokens referencing the data new input.
Traditionally, RETE-nets have not been applied to systems that process real-time data. A real-time system either guarantees a response to a change in critical data within a specific period of time, or simply guarantees a quick response. If there is a change in the facts in working memory, the inference engine must process those changes within a specified real-time period. Often real-time systems will quickly test data to determine if the change is "critical" and will continue with complex RETE-net processing only in critical cases. RETE-nets should respond to all data updates, not just critical changes.
Traditional RETE-nets are also ineffective in accepting real-time data input. Real-time data input, such as that from an environmental sensor, can create constant data changes. Most changes will be minor and incremental; most will not cause any rule to fire. Thus, there may be many inputs for a traditional RETE-net to process, but few inputs will cause right-hand side rule firing. However, even if there is no right-hand side firing caused by the incremental input, RETE-net state is constantly being updated. The inefficiency is due to the fact that the RETE-net nodes must constantly compare all values for even small changes in value.
In the past, programmers have employed various programming techniques to enhance real-time RETE-net performance. For example, RETE-net conditional test node structures have been modified to provide mechanisms that enable RETE-nets to respond only to critical changes in data, thereby preventing unnecessary data comparison and token passing. For further background on other techniques used to enhance RETE-net performance, reference can be made to pending U.S. patent application Ser. No. 499,039, filed Mar. 26, 1990 in the name of Ramakrishna, et al. entitled "A Reticular Discrimination Network for Specifying Real-Time Conditions", which is hereby expressly incorporated herein by reference.
Another problem is that the technique of procedural attachment has never been successfully applied to RETE-type pattern matching systems. Procedural attachment is the technique of automatically invoking user-defined functions whenever an access is made to a variable.
A procedural attachment is a set of instructions to be executed, whenever a designated variable is referenced. Procedural attachment programming techniques are based on an entity called a "procedurally attached variable" that associates the procedural attachments with data. For example, a variable "current-temp" can be associated with an attached set of instructions that will automatically execute whenever "current-temp" variable is referenced, such as, for example, printing the value of "current-temp" and the current time. Thus, a computer's execution of a program language statement: EQU current-temp&gt;max-temp
would cause the attached procedure to print all values of the current temperature until the current temperature has surpassed the max-temp value.
There are a variety of ways that procedural attachments can be attached to variables. A "write" procedural attachment comprises a set of instructions executed whenever an attached variable is written to. A "read" procedural attachment, described above, comprises a set of instructions executed whenever the value of an attached variable is referenced. A "modify" procedural attachment can execute a set of instructions whenever the value in the attached variable is modified.
Procedural attachment programming techniques have been developed for object-oriented systems but not RETE-nets. In object-oriented programming, data and instructions are combined into a single module of software known as an "object". Objects pass data and instructions between themselves, requesting information and giving instructions. For further background on the application of procedural attachment to object-oriented systems, reference can be made to Stefic, Bobrow and Kahn, "Integrated Access-Oriented Programming into a Multiple Paradigm Environment," IEEE Software, 10 (Vol. 3, No. 1 January 1986).
Reticular discrimination networks are similar to object-oriented systems in that rete-nodes pass tokens in a way analogous to how program objects exchange data and instructions. However, procedural attachment techniques can not currently be used successfully with reticular discrimination networks. The currently available methods of procedural attachment are either incompatible with RETE-type programming techniques or have large associated overhead, making procedural attachment techniques and computations very expensive to implement in RETE-net applications.
The problem of linking procedural attachments with RETE-net technology occurs with an attachment, known as a "read" procedure, being placed on variables that are evaluated as left-hand side conditions executed in RETE-net one-input and two-input join nodes. Others have attempted to provide procedural attachment techniques for left-hand side rule execution. Those attempts require repropagation and updating of all stored references to WME data on every cycle. That technique has an extremely high computational overhead and is, in a practical sense, unusable.
If procedural attachment techniques could be successfully applied in reticular discrimination networks, they would be especially useful in RETE-nets designed to interface with object-oriented languages, synchronize between WMEs and their expressions in external databases, and use RETE-nets to maintain a continuous watch on values supplied by external sensing devices.
Based on the foregoing, the structure of a RETE-net must be modified to allow an expert system to utilize procedural attachments in a practical manner.